// 给你一个字符串 s，找到 s 中最长的回文子串。

// 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

//暴力解法
function longestPalindrome(s: string): string {
  if (s.length === 1) {
    return s
  }
  const strlist: string[] = []
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j < s.length; j++) {
      const str = s.substring(i, j + 1)
      if (isPalindrome(str)) {
        strlist.push(str)
      }
    }
  }
  if (strlist.length === 0) {
    return s.charAt(0)
  }
  const longeststr = strlist.reduce((pre, cur) => {
    return cur.length > pre.length ? cur : pre
  })
  return longeststr
}

function isPalindrome(s: string): boolean {
  // console.log(s)
  if (s.length === 1) return true
  for (let l = 0, r = s.length - 1; l <= r; l++, r--) {
    if (s[l] !== s[r]) {
      return false
    }
  }
  return true
}

// 中心扩散法
function longestPalindrome2(s: string): string {
  let Resleft = 0;
  let Resright = 0;
  let maxLen = 0;
  let i = 0
  while (i < s.length) {
    let left = i - 1
    let right = i + 1
    
    while (left >= 0 && s.charAt(left) === s.charAt(i)) {
      
      left--
    }
    while (right < s.length && s.charAt(right) === s.charAt(i)) {
      right++
    }
    const end = right
    while (left >= 0 && right < s.length  && s.charAt(left) === s.charAt(right)) {
      left--
      right++
    }
    if (maxLen < right - left - 1) {
      maxLen = right - left - 1
      Resleft = left + 1
      Resright = right - 1
    }
    i = end
  }
  return s.substring(Resleft, Resright + 1)
}
console.log(longestPalindrome2('babad'))
